package com.demo.java.OD401_450.OD436;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【精准核酸检测(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146324700
 */
public class OdMain {
    // 用DFS遍历所有可能感染的人
    public static int findInfectedPeople(int[][] matrix, Set<Integer> confirmedCases) {
        int n = matrix.length;
        boolean[] visited = new boolean[n];
        Set<Integer> infected = new HashSet<>();

        // 对每个已确认感染的人进行DFS遍历
        for (int casePerson : confirmedCases) {
            dfs(casePerson, matrix, visited, infected);
        }

        // 从感染列表中去除原本已感染的人
        infected.removeAll(confirmedCases);
        return infected.size();  // 返回感染的人数
    }

    // 深度优先搜索 (DFS)，用于找到所有与已感染者接触的人
    private static void dfs(int person, int[][] matrix, boolean[] visited, Set<Integer> infected) {
        visited[person] = true;  // 标记该人已访问
        for (int i = 0; i < matrix.length; i++) {
            // 如果当前人和i有接触且i尚未被访问过
            if (matrix[person][i] == 1 && !visited[i]) {
                infected.add(i);  // 将i加入感染者列表
                dfs(i, matrix, visited, infected);  // 对i进行DFS遍历
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入人数N
        int n = scanner.nextInt();
        Set<Integer> confirmedCases = new HashSet<>();  // 已感染人员集合
        scanner.nextLine();  // 消耗换行符

        // 读取已感染人员的列表
        String[] confirmedCasesArray = scanner.nextLine().split(",");
        for (String confirmedCase : confirmedCasesArray) {
            confirmedCases.add(Integer.parseInt(confirmedCase));
        }

        // 读取接触矩阵
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] row = scanner.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                matrix[i][j] = Integer.parseInt(row[j]);
            }
        }

        // 计算输出结果
        int result = findInfectedPeople(matrix, confirmedCases);
        System.out.println(result);  // 输出感染人数
    }
}
